package game;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

public class NQueens {

	private static Integer[][] board = null;

	private static Integer[] placements = null;

	private static Map<Integer, List<Integer>> wrongPlacements = null;

	private static void play(int boardSize) {
		initBoard(boardSize);
		initPlacements(boardSize);
		placeAllQueens();
	}

	private static void placeAllQueens() {
		int size = board.length;
		for (int queen = 0; queen < size; ++queen) {
			if (placeQueen(queen)) {
				printBoard();
				printPlacements();
			} else {
				if (queen == 0) {
					System.out
							.println("No solution exists for this board size : "
									+ size);
					System.exit(1);
				} else {
					System.out
							.println("As placing Q"
									+ queen
									+ " has failed, trying repositioning previous queen Q"
									+ (queen - 1));
					wrongPlacements.get(queen - 1).add(placements[queen - 1]);
					for(int q = queen; q < size; q++) {
						wrongPlacements.get(q).clear();
					}
					board[queen - 1][placements[queen - 1]] = 0;
					placements[queen - 1] = -1;
					printBoard();
					printPlacements();
					placeAllQueens();
				}
			}

		}
	}

	private static boolean placeQueen(int queen) {
		if (placements[queen] != -1) {
			System.out.println("Q" + queen
					+ " is already correctly positioned...");
			return true;
		}
		System.out.println("Trying to place Q" + queen);
		int size = board.length;
		for (int column = 0; column < size; ++column) {
			System.out.println("\nChecking safety of cell -> "
					+ printMe(queen, column));
			if (chanceOfGettingKilled(queen, column)) {
				System.out.println(printMe(queen, column)
						+ " is DANGEROUS. Just continuing...");
			} else if (wrongPlacements.get(queen).contains(column)) {
				System.out.println(printMe(queen, column)
						+ " is tried previously and proved to be wrong.");
				if (wrongPlacements.get(queen).size() == size) {
					
					System.out
							.println("All places proved to be wrong for this queen Q"
									+ queen);
					if (queen == 0) {
						return false;
					}
					System.out.println("So try repositioning previous queen Q"
							+ (queen - 1));
					wrongPlacements.get(queen).clear();
					return false;
				} else {
					System.out.println("But, Still few more places to try..");
				}

			} else {
				System.out.println(printMe(queen, column) + " is SAFER.");
				placements[queen] = column;
				board[queen][column] = 1;
				System.out.println("Q" + queen + " is positioned safely @ "
						+ printMe(queen, column));
				return true;
			}
		}
		return false;
	}

	private static void initPlacements(int boardSize) {
		placements = new Integer[boardSize];
		wrongPlacements = new LinkedHashMap<Integer, List<Integer>>();
		Arrays.fill(placements, -1);
		for (int i = 0; i < boardSize; ++i) {
			wrongPlacements.put(i, new ArrayList<Integer>());
		}
		printPlacements();
	}

	private static void initBoard(int boardSize) {
		board = new Integer[boardSize][boardSize];

		for (Integer[] row : board) {
			Arrays.fill(row, 0);
		}

		System.out.println("Empty board!");
		printBoard();
	}

	public static void printPlacements() {
		System.out.println("Correct : " + Arrays.asList(placements));
		System.out.println("Wrong : " + wrongPlacements);
	}

	public static void printBoard() {
		int boardSize = board.length;

		for (int row = 0; row < boardSize; ++row) {
			System.out.println();
			for (int column = 0; column < boardSize; ++column) {
				System.out.print(board[row][column] == 0 ? " . " : " Q ");
			}
		}
		System.out.println();
	}

	public static boolean chanceOfGettingKilled(int row, int column) {
		return anyQueensAlreadyInThatRow(row)
				|| anyQueensAlreadyInThatColumn(column)
				|| possibleAttackFromOtherQueens(row, column);
	}

	private static boolean anyQueensAlreadyInThatColumn(int column) {
		for (Integer position : placements) {
			if (position == column) {
				System.out.println("Looks a Queen is already in COLUMN "
						+ column);
				return true;
			}
		}
		return false;
	}

	private static boolean possibleAttackFromOtherQueens(int row, int column) {
		List<Integer[]> diagonalIndices = getDiagonals(row, column);
		for (Integer[] diagonal : diagonalIndices) {
			if (placements[diagonal[0]] == diagonal[1]) {
				System.out
						.println("Looks already a queen is placed diagonally @ "
								+ stringify(diagonal));
				return true;
			}
		}
		return false;
	}

	private static List<Integer[]> getDiagonals(int x, int y) {
		List<Integer[]> diagonals = new ArrayList<Integer[]>();
		int size = board.length;
		for (int row = 0; row < size; ++row) {
			for (int column = 0; column < size; ++column) {
				if (((row + column) == (x + y)) || ((row - column) == (x - y))) {
					diagonals.add(new Integer[] { row, column });
				}
			}
		}
		return diagonals;
	}

	private static boolean anyQueensAlreadyInThatRow(int row) {
		boolean queenInThatRow = placements[row] != -1;
		if (queenInThatRow) {
			System.out.println("Looks a Queen is already in ROW " + row);
		}
		return queenInThatRow;
	}

	private static String stringify(Integer[] cell) {
		return " [" + cell[0] + ", " + cell[1] + " ]";
	}

	private static String printMe(int row, int column) {
		return " [" + row + ", " + column + " ]";
	}

	public static void main(String[] args) {
		NQueens.play(8);
	}
}
